package dailyTopic;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-05 10:57
 */
public class eventualSafeNodes802 {
    int index;
    int N=(int)1e4+10,M=4*N;
    int[] he=new int[N],e=new int[M],ne=new int[M];
    int[] cnt=new int[N];
    void add(int a,int b){
        e[index]=b;
        ne[index]=he[a];
        he[a]=index++;
    }
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n= graph.length;
        //he存反图cnt统计入度
        Arrays.fill(he,-1);
        for (int i = 0; i < n; i++) {
            for (int j: graph[i]) {
                add(j,i);
                cnt[i]++;
            }
        }
        //BFS，求拓扑排序
        Deque<Integer> d=new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (cnt[i]==0)
                d.addLast(i);
        }
        while (!d.isEmpty()){
            int p=d.pollFirst();
            for (int i = he[p]; i !=-1 ; i=ne[i]) {
                int j=e[i];
                if (--cnt[j]==0) d.addLast(j);
            }
        }
        List<Integer> res=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (cnt[i]==0) res.add(i);
        }
        return res;
    }
}
